package 二叉树;


import Utils.TreeNode;

import java.util.LinkedList;
import java.util.List;

/**
 * @author: TTDB
 * @create: 2025/9/17
 */
public class inorderTraversal {//中序遍历
        // 动态规划思路
        // 定义：输入一个节点，返回以该节点为根的二叉树的中序遍历结果
        public List<Integer> inorderTraversal(TreeNode root) {
            LinkedList<Integer> res = new LinkedList<>();
            if (root == null) {
                return res;
            }
            res.addAll(inorderTraversal(root.left));
            res.add(root.val);
            res.addAll(inorderTraversal(root.right));
            return res;
        }

        // 回溯算法思路
        LinkedList<Integer> res = new LinkedList<>();

        // 返回前序遍历结果
        public List<Integer> inorderTraversal2(TreeNode root) {
            traverse(root);
            return res;
        }

        // 二叉树遍历函数
        void traverse(TreeNode root) {
            if (root == null) {
                return;
            }
            traverse(root.left);
            // 中序遍历位置
            res.add(root.val);
            traverse(root.right);
        }
}
